import java.util.ArrayList;

public class Text3 {
    // 三角矩阵
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        int hang = triangle.size();
        if(hang == 0){
            return 0;
        }

        int[][] dp = new int[hang][hang];
        for(int i = hang - 1,j = 0; j < hang; j++){
            dp[i][j] = triangle.get(i).get(j);
        }

        for(int i = hang - 2; i >= 0; i--){
            for(int j = 0; j <= i; j++){
                dp[i][j] = Math.min(dp[i+1][j],dp[i+1][j+1]) + triangle.get(i).get(j);
            }
        }

        return dp[0][0];
    }
}
